/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/longest-word-in-dictionary
   @Language: C++
   @Datetime: 19-05-13 15:40
   */

class Solution {
public:
	/**
	 * @param words: a list of strings
	 * @return: the longest word in words that can be built one character at a time by other words in words
	 */
	string longestWord(vector<string> &words) {
		// Write your code here
		sort(words.begin(),words.end());
		unordered_set<string> dict(words.begin(),words.end());
		string maxword="";
		for(int i=0; i<words.size(); ++i){
			if(words[i].length()>1) continue;
			string word=words[i];
			queue<string> q;	//bfs
			for(q.push(word); q.size(); q.pop()){
				word=q.front();
				if(word.length()>maxword.length()) maxword=word;
				for(char ch='a'; ch<='z'; ++ch){
					word.push_back(ch);
					if(dict.count(word)) q.push(word);
					word.pop_back();
				}
			}
		}
		return maxword;
	}
};
